Tính chất Đồ_thị_hai

Tính chất Đồ_thị_hai_phía

Kích thước của phủ đỉnh nhỏ nhất bằng kích thước của cặp ghép lớn nhất
Kích thước của tập độc lập lớn nhất cộng kích thước của cặp ghép lớn nhất bằng số đỉnh.
Trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất bằng kích thước tập độc lập lớn nhất
Trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất cộng kích thước của phủ đỉnh nhỏ nhất bằng số đỉnh.
Một đồ thị là hai phía khi và chỉ khi có thể tô màu nó bằng hai màu.[8]
Quang phổ của một đồ thị là đối xứng khi và chỉ khi nó là một đồ thị hai phía.[9]

Liên quan

Tài liệu tham khảo